// //https://leetcode.cn/problems/container-with-most-water/
// //盛⽔最多的容器
// class Solution {
// public:
//     int maxArea(vector<int>& height) 
//     {
//         int bgein = 0;
//         int end = height.size() - 1;
//         int max = 0;
//         int num = 0;
//         while(bgein < end)
//         {
//             if(height[bgein] < height[end])
//             {
//                 num = height[bgein] * (end - bgein);
//                 bgein++;
//             }
//             else
//             {
//                 num = height[end] * (end - bgein);
//                 end--;
//             }
//             if(max < num)
//                 max = num;

//             // cout << max << ":" << bgein <<":" << end;
//             // cout << ":" << (end - bgein) << endl;
//         }
//         return max;
//     }
// };

// //https://leetcode.cn/problems/valid-triangle-number/
// // 有效三⻆形的个数

// class Solution 
// {
// public:
//     int triangleNumber(vector<int>& nums) 
//     {
//         sort(nums.begin(),nums.end());
//         int cnt = nums.size() - 1;
//         int num = 0;
//         while(cnt)
//         {
//             int left = 0;
//             int right = cnt - 1;

//             while(left < right)
//             {
//                 if(nums[left] + nums[right] > nums[cnt])
//                 {
//                     num += right -left;
//                     right--;
//                 }
//                 else
//                     left++;
//             }
//             cnt--;
//         }

//         return num;
//     }
// };

// //和为 s 的两个数字
// //https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/

// //暴力解法，不提供
// class Solution 
// {
// public:
//     vector<int> twoSum(vector<int>& price, int target) 
//     {
//         vector<int> nums;

//         sort(price.begin(),price.end());
//         int num = price.size();
//         while(num)
//         {
//             if(price[num-1] > target)
//             {
//                 num--;
//             }
//             else break;
//         }

//         for(int i = 0; i < num; i++)
//         {
//             for(int j = i + 1; j < num; j++)
//             {
//                 if(price[i] + price[j] == target)
//                 {
//                     nums.push_back(price[i]);
//                     nums.push_back(price[j]);
//                     return nums;
//                 }
//             }
//         }
//         return nums;
//     }
// };

// //双指针，利用单调性
// class Solution 
// {
// public:
//     vector<int> twoSum(vector<int>& price, int target) 
//     {
//         vector<int> nums;
//         int left = 0;
//         int right = price.size() - 1;
//         while(true)
//         {
//             if(price[left] + price[right] < target)
//             {
//                 left++;
//             }
//             else if(price[left] + price[right] > target)
//             {
//                 right--;
//             }
//             else
//             {
//                 nums.push_back(price[left]);
//                 nums.push_back( price[right]);
//                 break;
//             }
//         }
//         return nums;
//     }
// };

// //三数之和（medium）
// //https://leetcode.cn/problems/3sum/
// class Solution {
// public:
//     vector<vector<int>> threeSum(vector<int>& nums) {
//         vector<vector<int>> ret;
//         set<vector<int>> s;
//         sort(nums.begin(),nums.end());
        
//         int cnt = nums.size() - 1;
//         while(cnt)
//         {
//             int left = 0;
//             int rigth = cnt - 1;
//             while(left < rigth)
//             {
//                 if(nums[left] + nums[rigth] + nums[cnt] == 0)
//                 {
//                     vector<int> val = {nums[left],nums[rigth],nums[cnt]};
//                     s.insert(val);
//                     rigth--;
//                 }
//                 else if(nums[left] + nums[rigth] + nums[cnt] > 0)
//                 {
//                     rigth--;
//                 }
//                 else
//                     left++;
//             }
//             cnt--;
//         }

//         set<vector<int>>::iterator it = s.begin();
//         while(it != s.end())
//         {
//             ret.push_back(*it);
//             it++;
//         }

//         return ret;
//     }
// };


// class Solution {
// public:
//     vector<vector<int>> threeSum(vector<int>& nums) {
//         vector<vector<int>> ret;
//         sort(nums.begin(),nums.end());
        
//         int cnt = nums.size() - 1;
//         while(cnt)
//         {
//             int left = 0;
//             int rigth = cnt - 1;
//             while(left < rigth)
//             {
//                 if(nums[left] + nums[rigth] + nums[cnt] == 0)
//                 {
//                     vector<int> val = {nums[left],nums[rigth],nums[cnt]};
//                     ret.push_back(val);
//                     int num = nums[left++];
//                     while(left < rigth)
//                     {
//                         if(nums[left] != num) break;
//                         else left++;
//                     }

//                     num = nums[rigth--];
//                     while(left < rigth)
//                     {
//                         if(nums[rigth] != num) break;
//                         else rigth--;
//                     }
//                 }
//                 else if(nums[left] + nums[rigth] + nums[cnt] > 0)
//                 {
//                     int num = nums[rigth--];
//                     while(left < rigth)
//                     {
//                         if(nums[rigth] != num) break;
//                         else rigth--;
//                     }
//                 }
//                 else
//                 {
//                     int num = nums[left++];
//                     while(left < rigth)
//                     {
//                         if(nums[left] != num) break;
//                         else left++;
//                     }
//                 }
                    
//             }
//             int val = nums[cnt--];
//             while(cnt > 0)
//             {
//                 if(nums[cnt] != val) break;
//                 else cnt--;
//             }
            
//         }
//         return ret;
//     }
// };


// //最优解
// class Solution {
// public:
//     vector<vector<int>> threeSum(vector<int>& nums) {
//         vector<vector<int>> ret;
//         sort(nums.begin(),nums.end());
        
//         int cnt = nums.size() - 1;
//         while(cnt)
//         {
//             int left = 0;
//             int rigth = cnt - 1;
//             while(left < rigth)
//             {
//                 if(nums[left] + nums[rigth] + nums[cnt] == 0)
//                 {
//                     ret.push_back({nums[left],nums[rigth],nums[cnt]});
//                     left++;
//                     rigth--;
//                     while(left < rigth && nums[rigth + 1] == nums[rigth]) rigth--;   
//                     while(left < rigth && nums[left - 1] == nums[left]) left++;         
//                 }
//                 else if(nums[left] + nums[rigth] + nums[cnt] > 0)
//                 {
//                     rigth--;
//                 }
//                 else
//                 {
//                     left++;
//                 }
//             }
//             cnt--;
//             while(cnt > 0 && nums[cnt + 1] == nums[cnt]) cnt--;
            
//         }
//         return ret;
//     }
// };

//四数之和
//https://leetcode.cn/problems/4sum/
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());
        for(int i = 0; i < nums.size();)
        {
            for(int j = i + 1; j < nums.size(); )
            {
                if(j + 1 >= nums.size())
                    break;
                int left = j + 1;
                int right = nums.size() - 1;
                while(left < right)
                {
                    long long num = target - (long long)nums[i] - (long long)nums[j] - (long long)nums[left] - (long long)nums[right];
                    if(num > 0)
                        left++;
                    else if(num < 0)
                        right--;
                    else
                    {
                        ret.push_back({nums[i],nums[j],nums[left],nums[right]});
                        right--;
                        left++;
                        while(left < right && nums[right] == nums[right + 1]) right--;
                        while(left < right && nums[left] == nums[left - 1]) left++;
                    }
                }
                j++;
                while(j < nums.size() && nums[j] == nums[j - 1]) j++;

            }
            i++;
            while(i < nums.size() && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

